package leetcode.top100.Code33_FindTargetInRotateArr;

import offerbook.Code08_FindMinInRotateArr;

/**
 * 拓展。可能存在重复元素
 * 旋转数组找最小值。
 * [1,2,3,4,5,6] -> [4,5,6,1,2,3]
 *
 *  [0,1,1,1,1] -> [1,0,1,1,1] 或[1,1,0,1,1]等
 * 分析见{@link Code08_FindMinInRotateArr}
 * @date 2020/3/24 16:24
 */
public class Code153_FindMin2 {

    public static int findMin(int[] arr) {
        if(arr == null || arr.length == 0) throw new RuntimeException("illegal");
        if(arr.length == 1) return arr[0];
        //如果没有旋转
        if(arr[0] < arr[arr.length-1]) return arr[0];
        //二分查找
        int l = 0; //l只会向着左侧数组的最大值靠近，但是不会超出
        int r = arr.length -1;//r只会想着右侧数组的最小值靠近，但不会超出
        while (l < r){
            int mid = (r+l) >> 1;
            if(r - l == 1){
                return arr[r];
            }
            //[0,1,1,1,1] -> [1,0,1,1,1] 或[1,1,1,0,1]等.分不清，顺序查找
            if(arr[l] == arr[mid] && arr[l] == arr[r]){
                return inOrder(arr,l,r);
            }
            //在左侧的数组中
            if(arr[l] < arr[mid]){
                l = mid;
            }else {//在右侧的数组中。
                r = mid;
            }
        }
        return -1;
    }

    private static int inOrder(int[] arr, int l, int r) {
        int min = arr[l++];
        while (l <= r){
            min = Math.min(arr[l++],min);
        }
        return min;
    }

    public static void main(String[] args) {
        int[]arr1 = {1,0,1,1,1};
        int[]arr2 = {1,1,1,0,1};
        System.out.println(findMin(arr1));
        System.out.println(findMin(arr2));
    }
}
